package com.iris.dataStructures;

import java.util.Arrays;

/**
 *
 */
public class QuickSort2 {
    public static void main(String args[])
    {
        QuickSort2 quicksort = new QuickSort2();
        int[] arrays = new int[]
//                { 10, 12, 5, 13, 3, 14, 4, 15, 2, 16, 17, 17, 177, 18, 8, 8, 19 };
                { 10, 12};
        System.out.println("==========init==============");
        System.out.println(Arrays.toString(arrays));
        System.out.println("==========begin==============");
        int[] arraysNew = quicksort.quickSort(arrays,0,arrays.length-1);
        System.out.println("============end============");
        System.out.println(Arrays.toString(arraysNew));
    }
    public static int[] quickSort(int[] arr, int left, int right) {
        int  partitionIndex;

        if (left < right) {
            partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex-1);
            quickSort(arr, partitionIndex+1, right);
        }
        return arr;
    }

    public static int partition(int[] arr,int left ,int right) {     // 分区操作
        int pivot = left, index = pivot + 1;
        System.out.println("partition==========for begin ");
        for (int i = index; i <= right; i++) {
            //i =1 i =2 arr[2](2) < arr[0](10)  替换 arr[2] arr[1]
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
                System.out.println(Arrays.toString(arr)+"=====index="+index+",i="+i);
            }
        }
        swap(arr, pivot, index - 1);
        System.out.println(Arrays.toString(arr));
        System.out.println("partition==========for end ==index="+index);
        return index-1;
    }

    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
